package leetcode

import kotlinetc.println

//https://leetcode.com/problems/first-missing-positive/

/**
Given an unsorted integer sort.getArray, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3
Example 2:

Input: [3,4,-1,1]
Output: 2
Example 3:

Input: [7,8,9,11,12]
Output: 1
 */
//Classic
fun main(args: Array<String>) {

    firstMissingPositive(intArrayOf(-1, 0, 2, 2, 3, 5, 6, 7, 8, 9, 10)).println()
}

/**
 * 因为要求是常数级别空间复杂度，所以思路是 把 num[i] 的值放到 nums[i]-1的位置,
 * 也就是 1放到 索引0的位置，2放到索引1的位置，3到索引2的位置，最后从头遍历一遍，如果i位置上的值不是i+1就表明是缺失的i+1
 */
fun firstMissingPositive(nums: IntArray): Int {

    val size = nums.size

    for (i in 0 until size) {
        //这里不能写if，因为每次交换后nums[i]位置上的值已经变了，所以需要用一个while循环
        //虽然有两层循环，实际上只会对每个数字遍历一次
        while (nums[i] in 1..size && nums[nums[i] - 1] != nums[i]) {
            val tmp = nums[nums[i] - 1]
            nums[nums[i] - 1] = nums[i]
            nums[i] = tmp
        }
    }

    for (j in 0 until size) {
        if (nums[j] != j + 1) return j + 1
    }

    return size + 1
}

/**
 * 题目要求是常数级别的空间复杂度，时间复杂度是线性的
 * 在不考虑空间复杂度的情况下的解法:
 * 遍历两遍，第一次吧所有的数存入 set ，第二次从1开始在 set 中找，招不到就返回，如果一直找到最大的值
 * 返回 最大值+1

 */
fun firstMissingPositive1(nums: IntArray): Int {

    return 0
}
